让最小值减去最大值,就一定可以得到 \(n\) 个不同的差值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public static void solve () { int n = io.nextInt(); int [] a = new int [n]; for (int i = 0 ; i < n; i++) { a[i] = io.nextInt(); } var aux = new Integer [n]; for (int i = 0 ; i < n; i++) { aux[i] = i; } Arrays.sort(aux, (i, j) -> a[i] - a[j]); int [] ans = new int [n]; for (int i = 0 ; i < n; i++) { int t = aux[i]; ans[t] = n - i; } for (int i = 0 ; i < n; i++) { io.print(ans[i] + " " ); } io.println(); }
算是简单的分类讨论,比赛时写的稀烂。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public static void solve () { int n = io.nextInt(), cnt = 0 ; char [] s = io.next().toCharArray(); for (int i = 0 ; i < n / 2 ; i++) { if (s[i] != s[n - i - 1 ]) { cnt++; } } StringBuilder sb = new StringBuilder (); for (int i = 0 ; i <= n; i++) { if (i < cnt || i > n - cnt || (i - cnt) % 2 == 1 && n % 2 == 0 ) { sb.append('0' ); } else { sb.append('1' ); } } io.println(sb); }
比赛调试一小时,疯狂超时,结果是限制太强的原因。(浪费时间。)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public static void solve () { int n = io.nextInt(); int [] s = new int [n]; for (int i = 0 ; i < n; i++) { s[i] = io.nextInt(); } Arrays.sort(s); int x = n; for (int i = 0 ; i < n ; i++) { if (s[i] != i) { x = i; break ; } } while (x != -1 ) { io.println(x); io.flush(); x = io.nextInt(); } }
做了一个多小时 AC,有点像之前做的内向基环树,该题每个点都有个出边,所以至少有一个环。首先要特判 \(k=1\) 的情况,该情况每个位置都必须自成一个环,即 \(a_{i}=i\);其他情况所有环的长度都必须为 \(k\),这样可以保证答案存在。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 public static void solve () { int n = io.nextInt(), k = io.nextInt(); int [] b = new int [n]; for (int i = 0 ; i < n; i++) { b[i] = io.nextInt() - 1 ; } int [] in = new int [n]; for (int i = 0 ; i < n; i++) { in[b[i]]++; } Queue<Integer> q = new LinkedList <>(); for (int i = 0 ; i < n; i++) { if (in[i] == 0 ) { q.offer(i); } } while (!q.isEmpty()) { int x = q.poll(); if (--in[b[x]] == 0 ) { q.offer(b[x]); } } int cnt = 0 ; boolean [] vis = new boolean [n]; for (int i = 0 ; i < n; i++) { if (in[i] == 0 || vis[i]) continue ; int len = 0 ; for ( ; !vis[i]; i = b[i]) { vis[i] = true ; len++; } if (len != k) { io.println("NO" ); return ; } cnt++; } if (k == 1 && cnt != n) { io.println("NO" ); } else { io.println("YES" ); } }
注意,\(n\) 和 \(k\) 都是偶数!手推的话可能可以做出来吧。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public static void solve () { int n = io.nextInt(), k = io.nextInt(); int ans = 0 , i; for (i = 1 ; i + k - 1 <= n; i += k) { io.println("? " + i); io.flush(); ans ^= io.nextInt(); } for (; i <= n; i++) { io.println("? " + (i - k + 1 )); io.flush(); ans ^= io.nextInt(); } io.println("! " + ans); io.flush(); }
技巧性有点强,真想不到。就是如果多出一部分,可以通过两次异或算出来。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public static void solve () { int n = io.nextInt(), k = io.nextInt(); int ans = 0 , i; for (i = 1 ; i + k - 1 <= n; i += k) { io.println("? " + i); io.flush(); ans ^= io.nextInt(); } int t = n - i + 1 ; io.println("? " + (n - k + 1 - t / 2 )); io.flush(); ans ^= io.nextInt(); io.println("? " + (n - k + 1 )); io.flush(); ans ^= io.nextInt(); io.println("! " + ans); io.flush(); }